package org.example.sward.tooffer;

import java.util.Stack;

/**
 * <p>
 * Description:https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/59zt5i/
 * <p>
 * Copyright: 天津联想协同科技有限公司
 * <p>
 *
 * @author anlu
 * @date 2022/2/15 17:10
 */
public class Offer27 {

      public class TreeNode {
          int val;
          TreeNode left;
          TreeNode right;
          TreeNode(int x) { val = x; }
      }

    public static void main(String[] args) {
        Offer27 offer27 = new Offer27();
//        offer27.mirrorTree();
    }

    /**
     * 深度遍历替换 从上到底部
     * @param root
     * @return
     */
    public TreeNode mirrorTree(TreeNode root) {
          //递归的终止条件
        if(root == null){
            return null;
        }
        TreeNode temp = root.left;
        root.left = mirrorTree(root.right);
        root.right = mirrorTree(temp);
        return root;
    }

    /**
     * 广度优先遍历
     * @param root 根目录
     * @return
     */
    public TreeNode solution1(TreeNode root){
        if(root == null){
            return null;
        }
        Stack<TreeNode> stack = new Stack<TreeNode>();
        //初始化根节点
        stack.add(root);
        while (!stack.isEmpty()){
            //弹出最顶层的元素
            TreeNode node = stack.pop();
            if(node.left != null){
                stack.add(node.left);
            }
            if(node.right != null){
                stack.add(node.right);
            }
            TreeNode tmp = node.left;
            node.left = node.right;
            node.right = tmp;
        }
        return root;
    }


}
